package chapter23;

import java.util.*;

/**
 * 最小生成树-kruskal
 */
public class MST_kruskal {

    public static List<EdgeNode> kruskal(Graph G) {
        List<EdgeNode> A = new ArrayList<>();
        List<EdgeNode> edges = new ArrayList<>();
        for (VertexNode v : G.adjList) {
            EdgeNode pre = v.firstEdge;
            while (pre != null) {
                markSet(pre);
                if (!pre.key.equals(pre.firstEdge.key)) {
                    edges.add(pre);
                }
                pre = pre.next;
            }
        }
        sort(edges);
        for (EdgeNode edge : edges) {
            EdgeNode u = G.adjList.get(edge.firstEdge.adj).firstEdge;
            EdgeNode v = G.adjList.get(edge.adj).firstEdge;

            if (!findSet(u).key.equals(findSet(v).key)) {
                A.add(edge);
                union(u, v);
            }
        }
        return A;
    }

    public static void markSet(EdgeNode edge) {
        edge.p = edge;
        edge.rank = 0;
    }

    public static EdgeNode findSet(EdgeNode x) {
        if (!x.key.equals(x.p.key)) {
            x = findSet(x.p);
        }
        return x.p;
    }

    public static void union(EdgeNode x, EdgeNode y) {
        link(findSet(x), findSet(y));
    }

    private static void link(EdgeNode x, EdgeNode y) {
        if (x.rank > y.rank) {
            y.p = x;
        } else {
            x.p = y;
            if (x.rank == y.rank) {
                y.rank++;
            }
        }
    }

    public static void sort(List<EdgeNode> edges) {
        sort(edges, 0, edges.size() - 1);
    }

    private static void sort(List<EdgeNode> edges, int p, int r) {
        if (p < r) {
            int q = partition(edges, p, r);
            sort(edges, p, q - 1);
            sort(edges, q + 1, r);
        }
    }

    private static int partition(List<EdgeNode> edges, int p, int r) {
        EdgeNode edge = edges.get(r);
        int i = p - 1;
        for (int j = p; j <= r - 1; j++) {
            if (edges.get(j).weight < edge.weight) {
                i++;
                EdgeNode temp = edges.get(j);
                edges.set(j, edges.get(i));
                edges.set(i, temp);
            }
        }
        EdgeNode temp = edges.get(i + 1);
        edges.set(i + 1, edges.get(r));
        edges.set(r, temp);
        return i + 1;
    }

    public static void insert(EdgeNode x, EdgeNode y, int w) {
        EdgeNode pre = x;
        while (pre.next != null) {
            pre = pre.next;
        }
        y.firstEdge = x;
        y.weight = w;
        pre.next = y;
    }

    public static class EdgeNode {
        public String key;
        public int weight;
        public EdgeNode p;
        public EdgeNode firstEdge = this;
        public EdgeNode next;
        public boolean visit;
        public int adj;
        //
        public int rank;

        public EdgeNode(String key, int adj) {
            this.key = key;
            this.adj = adj;
        }

        public int getWeight() {
            return weight;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            EdgeNode edgeNode = (EdgeNode) o;
            return Objects.equals(key, edgeNode.key);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key);
        }

        @Override
        public String toString() {
            return "EdgeNode{" +
                    "u=" + firstEdge.key +
                    ", v='" + key + '\'' +
                    ", w=" + weight +
                    ", visit=" + visit +
                    '}';
        }
    }

    public static class VertexNode {
        public String key;
        public EdgeNode firstEdge;

        public VertexNode(EdgeNode firstEdge) {
            this.firstEdge = firstEdge;
        }

        @Override
        public String toString() {
            return "VertexNode{" +
                    "key='" + key + '\'' +
                    ", firstEdge=" + firstEdge +
                    '}';
        }
    }

    public static class Graph {
        public List<VertexNode> adjList = new ArrayList<>();
        public int numVertexes;
        public int numEdges;

        @Override
        public String toString() {
            return "Graph{" +
                    "adjList=" + adjList +
                    ", numVertexes=" + numVertexes +
                    ", numEdges=" + numEdges +
                    '}';
        }
    }
}
